package com.leetcode;
import java.util.*;


public class Date250328 {
    public static void main(String[] args){

    }
}
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < nums.length;){
            if(nums[i] > 0){
                break;
            }
                int left = i + 1,right = len - 1;

                while(left < right){
                        if(nums[left] + nums[right] == -nums[i]){
//                            List<Integer> list = new ArrayList<>();
//                            list.add(nums[i]);
//                            list.add(nums[left]);
//                            list.add(nums[right]);
//                            ret.add(list);
                            ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                            left++;
                            right--;
                            while(left < right && nums[left] == nums[left - 1]) left++;
                            while(left < right && nums[right] == nums[right + 1]) right--;
                        }else if(nums[left] + nums[right] > -nums[i]){
                            right--;
                        }else left++;

                    }
                i++;
            while(i < len - 1 && nums[i] == nums[i-1]){
                i++;
            }

        }
        return ret;
    }
}